/**
 * 描述:java集合
 *  1.HashMap源码解析
 *      1.默认参数
 *          1.初始容量16
 *          2.负载因子0.75
 *          3.红黑树升级阈值8
 *          4.红黑树退化阈值6
 *          5.生成红黑树的链表最大阈值是64
 *      2.hashMap结构
 *          1.Node:链表，存储着hash值，key,value，下个节点
 *          2.table:存储着一个个Node链表
 *          3.size：保存hashmap长度
 *          4.threshold:扩容的阈值，等于容量 * 负载因子
 *      3.put
 *          1.put调用内部的putVal方法，先对key进行了hash
 *          2.检查table是否为空，为空则resize()操作初始化容量
 *          3.以数组长度 - 1和hash值进行与运算，得出在table中的索引
 *          4.判断这个位置的node是否为空，为空则新建一个节点
 *          5.不为空则说明指定位置的node已经存在值，这时候出现hash碰撞
 *          6.判断key和hashCode是否相同，相同则直接替换当前的value
 *          7.不同则判断node节点是红黑树还是链表
 *          8.红黑树的话则直接查询红黑树，再判断hashCode和key是否有相等的节点，有的话替换，没有则新增
 *          9.如果是链表则相同的判断，key不同则插入到最后
 *          10.如果链表插入了节点后，会判断当前的链表长度是否会大于8，如果大于8并且当前table的长度大于64，
 *         则转为红黑树，否则进行resize()操作，扩容并且重hash
 *          11.最后回到那个节点，如果为空则返回Null，不为空则返回旧的值
 *      4.get
 *          1.将key hash，查询table是否为空，不为空计算出node节点的索引
 *          2.判断node节点是否为空，不为空判断是否为红黑树，红黑数的话执行红黑树的查询节点方法
 *          3.链表的话执行链表的查询，返回值
 *      5.remove
 *          1.先用跟get类似的方法查询出key和hashCode相同的那个节点，查询不到直接返回
 *          2.查询到之后，得到node节点，再执行移除方法，将大小减一，返回node值
 *      6.revise
 *          1.生成一个新的node数组，长度是原来的两倍，阈值也重新赋值为  新数组的长度 * 负载因子
 *          2.遍历旧的node数组，判断索引上的节点是否为一个，为一个的话直接重hash
 *          3.为红黑树则执行红黑树的重hash
 *          4.为链表的话，会让节点与旧的长度与操作，如果为0，则不需要移动，否则需要移动位置，位置为当前索引位置 + 旧的容量，采用尾插法
 *      7.为什么初始化大小是16
 *          1.因为获取索引的函数是(n-1) & hash ， 16-1=15 ，15是1111，其实就是提高运算效率，保证hash的均匀分布
 *          2.16只是作者认为合理的数量
 *      8.为什么hashmap可以存Null，hashtable不行
 *          1.因为hashmap key == 0 时候，hashcode = 0
 *      9.快速失败：java集合的一种机制，在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了
 *          修改，则会抛出异常。集合内部用modeCount记录是否删除了元素，如果modeCode跟期望的值不一样，则异常
 *      10.安全失败：concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改
 *      11.HashMap1.7和1.8有什么区别
 *          1.在node数组扩容的时候，会调用resize()方法，会新增一个容量是原来的两倍的node数组，然后重新
 *          hash存入，如果node是链表的话，里面的每个节点都会从头部插入到新的node节点中，在并发情况下会
 *          产生环形链表，导致死循环出现，所以1.8改成了尾插法
 *          2.1.8引入了红黑树，在Node链表的节点大于等于8的时候，就会触发升级成红黑树的操作，查询时间复杂度变为logn,
 *          在红黑树的节点数量小于等于6的时候，又会退化成链表
 *          3.jdk1.7是先扩容后进行插入，jdk1.8是先插入后进行扩容
 *          4.扩容后的存储位计算方式不同，1.7是重新hash一便，1.8是原位置or原位置 + 旧容量
 *      12.扰动函数 hash(key)，加大随机性
 *      13.HashMap源码中在计算hash值的时候为什么要右移16位
 *          1.尽量打乱hashCode真正参与位运算的低16位，因为比如是15的二进制为 16个0然后1111，跟hash值进行位运算都是0，
 *            而右移16位，可以直接将有用的部分进行hash，加大随机性，均匀分布
 *      14.什么时候进行扩容：
 *          1.在转红黑树的时候，判断节点node节点大于8但是table数组长度小于64
 *          2.添加完数据，判断是否大于阈值，阈值为 长度*0.75，大于的话则扩容
 *      15.为什么负载因子是0.75
 *          1.如果为1的话，那么会产生更多的hash碰撞，链表更可能转为红黑树，红黑树的插入需要时间的平衡，牺牲了时间，换取了空间
 *          2.如果为0.5的话，hash冲突减少了，但是链表也短了，容易进行扩容，牺牲了空间，换区了时间
 *          3.而0.75，源码上写了，是一种空间与时间上的权衡，即能减少hash冲突，又能提升空间效率
 *      16.为什么红黑树的阈值是8
 *          1.根据泊松分布，链表的长度为8的概率为百万分之一，其实不容易达到，所以选了这个。但是这个推测是在理想状态下，
 *            不理想的状态是hash算法不太行，导致了大量的冲突，链表的查询方式是便利，时间复杂度高，所以引入红黑树
 *      17.为什么红黑树退化阈值是6
 *          1.如果是7的话，那一删除就退化，频繁的转化与退化所花费的时间太多，所以以7为临界，选择了7
 * 2.concurrentHashMap源码解析
 *      1.put
 *          1.判断key是否为Null，concurrentHashMap不允许null的key和值，否则抛出异常
 *          2.spread()函数根据Key获取hash值 (h ^ (h >>> 16)) & HASH_BITS;
 *          3.自选操作保证能插入成功,如果Table是Null，则进行initTable
 *          4.初始化结束则进行hash取模，获取node的索引位置，如果为空，采用CAS设置值casTabAt，失败则自旋直到插入成功
 *          5.如果索引位置不为空，判断MODED是否为-1，为-1代表是正在进行扩容中，则帮助扩容，返回扩容后的table
 *          6.不为-1的话，开始分段加锁，synchronized锁住Node，判断当前Node是链表还是红黑树
 *          7.链表则循环判断每个节点的key和hash是否一致，一致替换，不一致则插入一个新的节点到链表末尾
 *          8.红黑树的话则执行树节点的替换或者插入
 *          9.设置完成值之后判断链表的节点大小是否大于等于8，并且目前的table大小是否大于64，满足这两条件则将此链表进化成红黑树，否则扩容重hash
 *          10.执行节点插入成功，增加size（addCount），用的baseCount + CounterCells数组中所有元素的size()
 *      2.initTable
 *          1.当sizeCtl < 0，代表有其它线程在扩容，Thread.yield让出时间片
 *          2.采用CAS修改sizeCtl的值为-1，成功则进入扩容代码
 *          3.初始化table的大小为16，并且设置扩容阈值 sc = n - (n >> 2)
 *      3.addCount
 *          1.CAS 给baseCount + 1，并发一大可能失败，里面有一个复杂的实现保证+1的成功
 *          2.当容量达到一定的时候，就需要对table进行扩容
 *          3.会先判断sizeCtl是否小于0，说明已经有线程在进行扩容，否则继续扩容，执行transfer
 *      4.transfer
 *          1.计算每条线程处理桶的个数，多线程处理
 *          2.初始化新的数组的长度为原来的2倍
 *          3.新建一个占位对象ForwardingNode，用于标识数组该位置的桶已经迁移完毕，处于扩容中，扩容期间遇到查询操作，遇到转发节点，会把查询转发到新的数组上去
 *          4.用一个advance和finish控制是否迁移完所有桶，while确定当前线程要迁移的桶的范围
 *      5.调用扩容方法的地方
 *          1.addCount中BaseCount的值达到扩容的阈值触发
 *          2.helpTransfer扩容状态下其它线程对集合进行增删改查等操作时遇上ForwardingNode节点时触发
 *          3.putAll批量插入或者插入后发现链表长度达到8个或以上，但数组长度为64以下时触发
 *      6.面试讲的方式：
 *          1.介绍jdk1.7和jdk1.8的区别
 *              1.jdk1.7采用的是segment,hashEntry数组的方式，采用的是分段锁技术，put方法需要进行两次hash，第一次hash是寻找segment的位置，第二次
 *                hash是在segment中寻找hashEntry的位置。segment继承的是reentrantLock，采用tryLock方式去尝试获取锁，锁的颗粒度是一个个segment；
 *                而jdk1.8采用的是cas + synchronized + table数组 + node链表 + 红黑树的结构，put方法只需要进行一次的hash，锁的颗粒度也降低到了
 *                每一个node节点，比jdk1.7低
 *              2.jdk1.8关键概念点
 *                  1.sizeCtl变量，用volatile修饰的，通过CAS操作 + volatile保证内存可见行，控制数组的初始化和扩容
 *                      1.-1表示正在初始化
 *                      2.-N前16位记录数组容量，后16位记录扩容线程大小+1，是个负数
 *                      3.正数0，表示未初始化
 *                      4.正数，0.75*当前数组大小，表示扩容阈值
 *                  2.ForwardingNode
 *                  3.table(volatile):就是数组，默认null，默认初始化大小16，每次扩容两倍
 *                  4.nextTable(volatile)：扩容时新生成的数组，大小为table的两倍
 *              3.put函数
 *                  1.首先调用spread函数，计算hash值，之后进入一个自旋循环过程，直到插入或替换成功，才会返回。如果table未被初始化，则调用initTable进行初始化。
 *                    之后判断hash映射的位置是否为null,如果为null,直接通过CAS自旋操作，插入元素成功，则直接返回，如果映射的位置值为MOVED(-1),则直接去协助扩容，
 *                    排除以上条件后，尝试对链头Node节点f加锁，加锁成功后，链表通过尾插遍历，进行插入或替换。红黑树通过查询遍历，进行插入或替换。之后如果当前链表
 *                    节点数量大于阈值，则调用treeifyBin函数转换为红黑树最后通过调用addCount,执行CAS操作，更新数组大小，并且判断是否需要进行扩容。
 *              4.spread函数
 *                  1.spread函数，计算hash值。key的hash值与其高16位相异或，然后与HASH_BITS将最高位置0
 *              5.addCount函数
 *                  1.每次添加完元素后，数量+1，判断是否扩容，达到则扩容或者协助扩容
 *                  2.元素个数的存储方式类似LongAdder，如果baseCount存在竞争，则写入到不同的段上，减少不同线程更新size的冲突
 *                  3.计算元素个数时，将baseCount和各个cell的数量相加，得到当前的总数
 *                  4.sizeCtl保存跟扩容相关的信息，如果有其它线程进来，会协助扩容
 *              6.initTable函数(下文将扩容和初始化，统称为扩容)
 *                  1.进入一个自旋过程，一旦有线程扩容成功，才break
 *                  2.如果sizeCtl < 0,说明已经有线程正在扩容，所以直接让出线程
 *                  3.如果sizeCtl>=0,说明当前没有线程扩容，尝试CAS操作，设置sizeCtl为-1
 *                  4.设置sizeCtl为-1成功的线程，进行扩容操作，并且将sc更新为数组负载阈值0.75*n
 *              7.transfer
 *                  1.生成一个两倍于原来的nextTable
 *                  2.迁移元素先从靠后的桶开始，迁移完成的桶在里面放置一个ForwadingNode节点，标记该桶元素迁移完成，如果这时候访问旧的桶，会指向到新的nextTable中
 *                  3.迁移过程中通过判断hash&n是否等于0，判断迁移后的索引下标位置，为0的位置跟原来一样，不为0的则位置为旧的容量大小 + 当前索引位置
 *                  4.迁移元素的时候会锁住当前的桶，分段锁原理
 *              8.helpTransfer
 *                  1.协助扩容（迁移元素），当线程添加元素时发现table正在扩容，且当前元素所在的桶元素已经迁移完成了，则协助迁移其它桶的元素。
 *                    当前桶元素迁移完成了才去协助迁移其它桶元素
 *              9.get
 *                  1.hash到元素所在的桶
 *                  2.如果桶中第一个元素就是该找的元素，直接返回
 *                  3.如果是树或者正在迁移元素，则调用各自Node子类的find()方法寻找元素
 *                  4.如果是链表，遍历整个链表寻找元素
 *                  5.获取元素没有加锁
 *              10.remove
 *                  1.计算hash,如果所在的桶不存在，表示没有找到目标元素，返回
 *                  2.如果正在扩容，则协助扩容完成后再进行删除操作
 *                  3.如果是以链表形式存储的，则遍历整个链表查找元素，找到之后再删除;如果是以树形式存储的，则遍历树查找元素，找到之后再删除;如果是以树形式存储的，删除元素之后树较小，则退化成链表
 *                  4.如果确实删除了元素，则整个map元素个数减1，并返回旧值
 *                  5.如果没有删除元素，则返回null
 *
 * 3.阻塞队列
 *      1.当队列是空的时候，从队列中获取元素都会被阻塞；当队列是满的时候，往队列中添加元素的操作会被阻塞
 *      2.类型：
 *          1.ArrayBlockingQueue：数组构成的有界阻塞队列
 *          2.LinkedBlockingDeque;由链表结构组成的有界（但大小默认值为Integer.MAX_VALUE）阻塞队列
 *          3.PriorityBlockingQueue;支持优先级排序的无界阻塞队列
 *          4.DelayQueue;使用优先级队列实现的延迟无阻塞队列
 *          5.SynchronousQueue;不存储元素的阻塞队列，也即单个元素的队列
 *          6.Deque:双向链表结构
 *      3.ArrayBlockingQueue：
 *          1.ArrayBlockingQueue 是一个用数组实现的有界阻塞队列，其内部按先进先出的原则对元素进行排序，其中put方法和take方法为添加和删除的阻塞方法
 *          2.ArrayBlockingQueue内部的阻塞队列是通过重入锁ReenterLock和Condition条件队列实现的，所以ArrayBlockingQueue中的元素存在公平访问与非公平访问的区别
 *          3.当队列满时通过条件对象Condtion来阻塞当前调用put方法的线程，直到线程又再次被唤醒执行
 * 4.ArrayList
 *      1.属性
 *          1.默认初始化容量：final int DEFAULT_CAPACITY=10
 *          2.指定容量为0时，返回该数组：final Object[] EMPTY_ELEMENTDATA = {}
 *          3.不指定容量时候，返回该数组：final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
 *          4.transient Object[] elementData：保存添加到ArrayList中的元素，被标记为transient，在对象被序列化的时候不会被序列化
 *          5.size：list大小
 *          6.final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8：分派给arrays的最大容量，因为某些VM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致array容量大于VM的limit，最终导致OutOfMemoryError
 *      2.构造方法：
 *          1.ArrayList(int initialCapacity)：构造指定容量的数组
 *              1.初始容量大于0,实例化数组，将自定义的容量大小当成初始化elementData的大小
 *              2.初始容量等于0，将空数组赋给elementData，EMPTY_ELEMENTDATA
 *              3.初始容量小于0，抛异常
 *          2.ArrayList()：构造空的list，用的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，后面一添加元素，就会给定默认容量10
 *          3.ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表
 *              1.将collection对象转换成数组，然后将数组的地址的赋给elementData
 *              2.如果数组的实际大小等于0（c中没有元素），将空数组EMPTY_ELEMENTDATA赋值给elementData
 *              3.如果size的值大于0，则执行Arrays.copy方法，把collection对象的内容（可以理解为深拷贝）copy到elementData中
 *      3.get()方法：
 *          1.越界检查rangeCheck()
 *          2.通过数组下标来获取到元素，时间复杂度O1
 *      4.set()方法
 *          1.越界检查rangeCheck()
 *          2.通过数组下标获取到元素，记录旧的要被替换的元素
 *          3.替换元素
 *      5.add()方法：
 *          1.boolean add(E e)
 *              1.默认往数组的末尾添加一个元素
 *              2.进行数组的容量检查，传入ensureCapacityInternal(size + 1),不够则扩容
 *              3.将元素添加到size的位置上，size再加1 elementData[size++] = e
 *          2.void add(int index, E element)
                 public void add(int index, E element) {
                    //越界检查
                    rangeCheckForAdd(index);
                    //确认list容量，如果不够，容量加1。注意：只加1，保证资源不被浪费
                    ensureCapacityInternal(size + 1);  // Increments modCount!!
                    // 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素位移一个位置
                    //在插入元素之前，要先将index之后的元素都往后移一位
                    //arraycopy(原数组，源数组中的起始位置，目标数组，目标数据中的起始位置，要复制的数组元素的数量)
                    System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);
                    //将指定的index位置赋值为element
                    elementData[index] = element;
                    //实际容量+1
                    size++;
                 }
 *      6.grow方法：
 *          1.int oldCapacity = elementData.length:获取当前数组容量
 *          2.int newCapacity = oldCapacity + (oldCapacity >> 1)：相当于扩容到原来的1.5倍
 *          3.如果扩容后的容量还是小于想要的最小容量，将扩容后的容量再次扩容为想要的最小容量，elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，
 *            在这里就是真正的初始化elementData的大小了，就是为10
 *          4.如果扩容后的容量大于临界值，则进行大容量分配 newCapacity = hugeCapacity(minCapacity);
 *          5.elementData = Arrays.copyOf(elementData, newCapacity) ： 新的容量大小已经确定好了，就copy数组，改变容量大小
 *      7.remove方法：
 *          1.进行越界检查
 *          2.记录修改次数（modCount 可以用来检测快速失败的一种标志。）
 *          3.通过索引找到要删除的元素
 *          4.计算要移动的位数
 *          5.移动元素（其实是覆盖掉要删除的元素）
 *          6.将–size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它
 *          7.返回被删除的元素
 * 5.fail-fast（快速失败）机制和fail-safe（安全失败）
 *      1.区别：fail-safe允许在遍历的过程中对容器中数据进行修改，而fail-fast不允许
 *      2.fail-fast：直接在容器上遍历，遍历过程中发现数据被修改了（modcount++来判断），会立刻抛出异常，java.util包底下都是fail-fast的，比如hashMap和ArrayList
 *      3.这种遍历基于容器的一个克隆。因此，对容器内容的修改不影响遍历。java.util.concurrent包下的容器都是安全失败的,可以在多线程下并发使用,并发修改。
 *        常见的的使用fail-safe方式遍历的容器有ConcerrentHashMap和CopyOnWriteArrayList等
 *
 * @author Youjm
 * @created 2022/3/2 14:11
 */
public class JavaCollection {
    public static void main(String[] args) {

    }
}

/*HashMap源码*/
class HashMapCode {
//    /*默认容量16*/
//    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//    /*最大容量2的30次方*/
//    static final int MAXIMUM_CAPACITY = 1 << 30;
//    /*负载因子，扩容用的0.75f*/
//    static final float DEFAULT_LOAD_FACTOR = 0.75f;
//    /*升级成红黑树链表的数量是8*/
//    static final int TREEIFY_THRESHOLD = 8;
//    /*退化成红黑树链表的数量6*/
//    static final int UNTREEIFY_THRESHOLD = 6;
//    /*红黑树生成的阈值，如果node的数量小于64，则不生成红黑树，而是resize()重构链表*/
//    static final int MIN_TREEIFY_CAPACITY = 64;
//    /*允许key为null，hash为0，*/
//    static final int hash(Object key) {
//        int h;
//        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//    }

//    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
//                   boolean evict) {
//        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
//        if ((tab = table) == null || (n = tab.length) == 0)
//            n = (tab = resize()).length;  初始化容量
    //         为什么是(n-1) & hash???????
//        if ((p = tab[i = (n - 1) & hash]) == null)
//            tab[i] = newNode(hash, key, value, null);  如果当前的table数组为0个，则直接新增节点插入
//        else {
              //当前的table Node数组不为空的话，做如下处理
//            HashMap.Node<K,V> e; K k;
              //如果hash和key的值都相等的话，则直接替换
//            if (p.hash == hash &&
//                    ((k = p.key) == key || (key != null && key.equals(k))))
//                e = p;
              //如果 Node进化成了红黑树，则执行插入数据到红黑树的方法
//            else if (p instanceof HashMap.TreeNode)
//                e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//            else {
                  //否则从链表的后面插入
//                for (int binCount = 0; ; ++binCount) {
//                    if ((e = p.next) == null) {
//                        p.next = newNode(hash, key, value, null);
                          //如果链表节点阈值大于等于7，调用生成红黑树的方法
//                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//                            treeifyBin(tab, hash);
//                        break;
//                    }
                      //如果hash 和 key 都相等，那更新
//                    if (e.hash == hash &&
//                            ((k = e.key) == key || (key != null && key.equals(k))))
//                        break;
//                    p = e;
//                }
//            }
              //返回旧的值，onlyIfAbsent意思是如果存在key相同，是否执行替换
//            if (e != null) { // existing mapping for key
//                V oldValue = e.value;
//                if (!onlyIfAbsent || oldValue == null)
//                    e.value = value;
//                afterNodeAccess(e);
//                return oldValue;
//            }
//        }
//        ++modCount;
//        if (++size > threshold) //检查是否超过阈值，超过则重构链表，扩容
//            resize();
//        afterNodeInsertion(evict);
//        return null; 不存在相同的Key，则直接返回null
//    }

//    final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {
//        int n, index; HashMap.Node<K,V> e;
          //如果当前table是null或者table的大小小于红黑树生成的阈值，则resize()重构链表
//        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//            resize();
//        else if ((e = tab[index = (n - 1) & hash]) != null) {
//            HashMap.TreeNode<K,V> hd = null, tl = null;
//            do {
                  //生成红黑树
//                HashMap.TreeNode<K,V> p = replacementTreeNode(e, null);
//                if (tl == null)
//                    hd = p;
//                else {
//                    p.prev = tl;
//                    tl.next = p;
//                }
//                tl = p;
//            } while ((e = e.next) != null);
//            if ((tab[index] = hd) != null)
//                hd.treeify(tab);
//        }
//    }

//    final HashMap.Node<K,V>[] resize() {
//        HashMap.Node<K,V>[] oldTab = table;
//        int oldCap = (oldTab == null) ? 0 : oldTab.length;
//        int oldThr = threshold;
//        int newCap, newThr = 0;
//        if (oldCap > 0) {
//            if (oldCap >= MAXIMUM_CAPACITY) {
//                threshold = Integer.MAX_VALUE;
//                return oldTab;
//            }
              //旧的容量的两倍还小于最大容量，并且旧的容量大于默认容量，则将新的阈值设置为原来的两倍
//            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
//                    oldCap >= DEFAULT_INITIAL_CAPACITY)
//                newThr = oldThr << 1; // double threshold
//        }
//        else if (oldThr > 0) // initial capacity was placed in threshold
//            newCap = oldThr;
//        else {
              //老表的容量为0，老表的阈值为0，这种情况是初始化new的时候没有传入容量，则将初始容量和阈值设为默认
//            newCap = DEFAULT_INITIAL_CAPACITY;
//            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
//        }
         //如果新表的阈值为空，则通过新表容量 * 负载因子得到新表阈值
//        if (newThr == 0) {
//            float ft = (float)newCap * loadFactor;
//            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
//                    (int)ft : Integer.MAX_VALUE);
//        }
//        threshold = newThr;
//
//        HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
//        table = newTab;
          //如果老表不为空，则需便利所有节点，将节点赋值给新表，进行重hash
//        if (oldTab != null) {
//            for (int j = 0; j < oldCap; ++j) {
//                HashMap.Node<K,V> e;
//                if ((e = oldTab[j]) != null) {
//                    oldTab[j] = null;
//                    if (e.next == null)
                          //如果是单节点，则直接放入
//                        newTab[e.hash & (newCap - 1)] = e;
//                    else if (e instanceof HashMap.TreeNode)
                          //如果是红黑树节点，则进行红黑树的重hash分布
//                        ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//                    else {
                          //普通的链表节点，则尾插法插入
//                        HashMap.Node<K,V> loHead = null, loTail = null;
//                        HashMap.Node<K,V> hiHead = null, hiTail = null;
//                        HashMap.Node<K,V> next;
//                        do {
//                            next = e.next;
//                            if ((e.hash & oldCap) == 0) {
//                                if (loTail == null)
//                                    loHead = e;
//                                else
//                                    loTail.next = e;
//                                loTail = e;
//                            }
//                            else {
//                                if (hiTail == null)
//                                    hiHead = e;
//                                else
//                                    hiTail.next = e;
//                                hiTail = e;
//                            }
//                        } while ((e = next) != null);
//                        if (loTail != null) {
//                            loTail.next = null;
//                            newTab[j] = loHead;
//                        }
//                        if (hiTail != null) {
//                            hiTail.next = null;
//                            newTab[j + oldCap] = hiHead;
//                        }
//                    }
//                }
//            }
//        }
//        return newTab;
//    }

//    final HashMap.Node<K,V> getNode(int hash, Object key) {
//        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
          //判断table不为空，且table长度大于0且table的第一个节点不等于空
//        if ((tab = table) != null && (n = tab.length) > 0 &&
//                (first = tab[(n - 1) & hash]) != null) {
//            if (first.hash == hash && // 总是检查第一个节点
//                    ((k = first.key) == key || (key != null && key.equals(k))))
//                return first;
//            if ((e = first.next) != null) {  第一个节点是空的，则检查后面的，遍历红黑树查询或者遍历链表查询
//                if (first instanceof HashMap.TreeNode)
//                    return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
//                do {
//                    if (e.hash == hash &&
//                            ((k = e.key) == key || (key != null && key.equals(k))))
//                        return e;
//                } while ((e = e.next) != null);
//            }
//        }
//        return null;
//    }

//    final HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
//                                       boolean matchValue, boolean movable) {
//        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, index;
          //先查询出node，如果hash和Key都对的上，那么直接查询到，对不上则往下遍历，红黑树或者链表
//        if ((tab = table) != null && (n = tab.length) > 0 &&
//                (p = tab[index = (n - 1) & hash]) != null) {
//            HashMap.Node<K,V> node = null, e; K k; V v;
//            if (p.hash == hash &&
//                    ((k = p.key) == key || (key != null && key.equals(k))))
//                node = p;
//            else if ((e = p.next) != null) {
//                if (p instanceof HashMap.TreeNode)
//                    node = ((HashMap.TreeNode<K,V>)p).getTreeNode(hash, key);
//                else {
//                    do {
//                        if (e.hash == hash &&
//                                ((k = e.key) == key ||
//                                        (key != null && key.equals(k)))) {
//                            node = e;
//                            break;
//                        }
//                        p = e;
//                    } while ((e = e.next) != null);
//                }
//            }
              //查询出Node后，如果不为空则进行移除操作，判断红黑树移除还是链表移除
//            if (node != null && (!matchValue || (v = node.value) == value ||
//                    (value != null && value.equals(v)))) {
//                if (node instanceof HashMap.TreeNode)
//                    ((HashMap.TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//                else if (node == p)
//                    tab[index] = node.next;
//                else
//                    p.next = node.next;
//                ++modCount;
//                --size;
//                afterNodeRemoval(node);
//                return node;
//            }
//        }
//        return null;
//    }
}






